package leetcode.day_2020_2021_2_1_2021_2_7;

import java.util.Map;

/**
 * 32. 最长有效括号
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 * https://leetcode-cn.com/problems/longest-valid-parentheses/solution/dong-tai-gui-hua-si-lu-xiang-jie-c-by-zhanganan042/
 * dp[i]=dp[i−2]+2
 *
 * dp[i] = dp[i - 1] + dp[i - dp[i - 1] - 2] + 2dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
 *
 * 那么，求dp[i]dp[i]就变成了求dp[i - 1]dp[i−1]、 dp[i - 2]dp[i−2]、dp[i - dp[i - 1] - 2]dp[i−dp[i−1]−2]的子问题。
 *
 */
public class LeetCode0032 {
    public static void main(String[] args) {
        System.out.println(longestValidParentheses(")()())"));
        System.out.println(longestValidParentheses(")())()"));
        System.out.println(longestValidParentheses("()(())"));
    }

    public static int longestValidParentheses(String s) {
        int len = s.length();
        if (len <= 1) return 0;
        int[] dp = new int[len];
        char[] sArr = s.toCharArray();
        int maxVal = 0;
        for (int i=1; i<len; i++) {
            if (sArr[i] == ')') {
                if (sArr[i-1] == '(') {
                    dp[i] = 2;
                    if (i-2 > 0) {
                        dp[i] = dp[i-2] + dp[i];
                    }
                } else if (dp[i-1] > 0) {
                    if ((i-dp[i-1]-1 >0) && sArr[i-dp[i]-1]=='(') {
                        dp[i] = dp[i-2] + 2;
                        if (i-dp[i-1]-2 > 0) {
                            dp[i] = dp[i] + dp[i-dp[i-1]-2];
                        }
                    }
                }
            } else {
                dp[i] = dp[i-1];
            }
            maxVal = Math.max(maxVal, dp[i]);
        }
        return maxVal;
    }
}
